package 链表.单链表;


/**
 * https://leetcode.cn/problems/palindrome-linked-list/?favorite=2cktkvj
 */
public class _234_回文链表 {

    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 如果发送天指针没有指向null，说明链表长度为奇数，slow还要再向前面前进一步
        if(fast != null) {
            slow = slow.next;
        }

        ListNode h1 = head;
        ListNode h2 = reverNode(slow);

        while (h2 != null) {
            if(h1.val != h2.val) return false;
            h1 = h1.next;
            h2 = h2.next;
        }

        return true;
    }

    private ListNode reverNode(ListNode node) {
        if(node == null || node.next == null) return node;

        ListNode last = reverNode(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }
}
